1. Field of the Invention
The present invention relates to the field of computer image processing, and more specifically, selectively rendering objects in a scene in image processing systems.
2. Background Description
State of the art computer aided design (CAD) uses very complex models of objects, wherein each model may include a large number of polygons, that represent physical structures. Interactive visualization of these large polygonal models, places an enormous burden upon the current graphics hardware and makes image rendering very complex and time consuming. This complexity makes it impossible to render at interactive rates with state of the art hardware, especially when interactively rendering large 3D models and is a well known problem in the art. Consequently, numerous methods have been proposed to reduce, or cull, the number of polygons that are rendered for a particular viewpoint and scene model.
for example, one such approach, view frustum culling, does not render any polygons lying completely outside of the viewer""s field of view. Similarly, for rendering solid objects, those polygons that are facing away from the viewpoint (i.e., the back-facing polygons) may be omitted for rendering. Accordingly, a potentially greater reduction in the number of polygons that must be processed might be realized by culling away those geometric portions of the scene or shapes therein that are occluded from view by other objects in the forefront of the scene.
Another approach to this problem is discussed by S. Teller and C. Sequin in xe2x80x9cVisibility Preprocessing for Interactive Walkthroughs,xe2x80x9d SIGGRAPH 1991 Conference Proceedings, ACM Press, 1991, pp. 61-69. Teller and Sequin""s approach has been to break the input model down into xe2x80x9ccellsxe2x80x9d and xe2x80x9cportalsxe2x80x9d. Cells have boundaries coinciding with opaque surfaces, while portals represent non-opaque surfaces between the cells. An adjacency graph is constructed to connect the cells via portals. Then, the adjacency graph is utilized to determine the cell-to-cell visibility and the potentially visible set (PVS) of polygons for each cell. Unfortunately, the Teller and Sequin approach has been presented, typically, within a framework of architectural models wherein cells (e.g., floors, rooms, hallways) and portals (e.g., doors, windows) are easily defined. Teller and Sequin do not address more complicated scenarios, such as rendering general, large 3D models at interactive rates.
yet another approach is discussed by S. Coorg and S. Teller in xe2x80x9cTemporally Coherent Conservative Visibility,xe2x80x9d Proceedings, 12th Annual ACM Symposium of Computer Geometry, 1996, 78-87. Coorg and Teller also precompute a superset of the visible polygons when the viewpoint is within a particular region of space. As the viewpoint moves, the Coorg and Teller method tracks only those events that cause changes in the polygons visible from the current viewpoint, termed xe2x80x9cvisual eventsxe2x80x9d by Coorg and Teller. Unfortunately, the Coorg and Teller method considers only a single polygon as an occluder. Coorg and Teller rely on the model to include large occluders. However, the Coorg and Teller method does not handle scenes with an absence of large occluders or objects being occluded by multiple smaller objects well.
N. Greene, M. Kass and G. Miller in xe2x80x9cHierachical Z-Buffer Visibility,xe2x80x9d SIGGRAPH 93 Conference Proceedings, ACM Press, 1993, pp. 273-278, teach a Hierarchical Z-buffer (HZB) that extends the traditional Z-buffer by maintaining what is termed an xe2x80x9cimage Z pyramidxe2x80x9d to quickly reject hidden geometry. A second data structure, an octree, is built upon the geometry in object-space. At run-time, the octree is traversed with each node of the tree being queried against the current HZB. If a current node is determined to be behind previously visible geometry, then the current octree node can be skipped, together with all children of the skipped node and the geometry associated with children. Otherwise, as the image geometry is rendered, new z values are propagated for the current node through the HZB, as well as for the children of the current node. Unfortunately, to achieve interactive rendering rates, the HZB approach requires special graphics hardware to make the necessary queries and updates against the HZB.
Yet another approach, similar to the HZB approach, is the Hierarchical Occlusion Maps (HOM) of H. Zhang, D. Manocha, T. Hudson and K. E. Hoff III, xe2x80x9cVisibility Culling using Hierarchical Occlusion Maps,xe2x80x9d SIGGRAPH 97 Conference Proceedings, ACM Press, 1997, pp. 77-88. The HOM approach is similar to the HZB in using both object and image space hierarchies. Initially, the HOM image spaces are built by rendering shapes with a high potential for occluding, i.e., shapes that are very close to the current viewpoint. To determine visibility of the remaining shapes, the object space hierarchy is traversed while checking each node against a hierarchical occlusion map, using, if necessary, a conservative depth test to determine occlusion. However, the HOM approach requires initially selecting occluders to be rendered at each viewpoint. Further, to accelerate HOM shape construction, the HOM approach requires special graphics hardware to support bilinear interpolation of texture maps.
Thus, there is a need for efficiently selecting portions of geometry to be rendered in an image processing system that does not require special graphics hardware.
It is a purpose of the invention to improve image rendering in image processing systems;
It is another purpose of the invention to improve efficiency in selecting image portions rendered in an image processing system;
It is yet another purpose of the invention to improve selecting scene portions that are rendered and identifying occluded scene portions that are not rendered, thereby improving system efficiency;
It is yet another purpose of the invention to minimize scene geometry rendered while producing an image that is visually indistinguishable with the image resulting from rendering all of the scene geometry.
The present invention is a technique of occlusion culling and system therefor. The culling method of the present invention first determines which polygons are hidden, or occluded, by other objects. These hidden or occluded polygons will not contribute to the final scene and, therefore, need not be rendered. The present invention includes two major steps. In the first major step, the input models are preprocessed to build a hierarchical data structure which is used as an approximation to the input models. In this first step, simple polygonal occluders are determined for substitution in place of the complex image geometry in successive visibility queries. Once the first preprocessing step is complete, the second step may be executed at run-time, while a user is inspecting, or visualizing, the input. In the second step, the occluders, determined in the first step, are used to forego rendering shapes or shape portions that are unseen from the current viewpoint.